#ifndef _LIST_H_
#define _LIST_H_

/**********************************
write by zhangliang <liangzhws@foxmail.com>
**********************************/

#ifndef NULL

#define NULL     0

#endif 

#ifndef __BOOL
#define __BOOL

typedef int bool;

#define false    0
#define true     1

#endif


#ifndef _INIT_HEAD
#define _INIT_HEAD

#define init_head(type, head) init_head_##type(head)

#endif


#ifndef __ENTRY
#define __ENTRY

#define entry(ptr, type, member) (type *)((char *)(ptr) - (unsigned long)(&((type *)0)->member))

#endif

/************************************
list  model:
	------
       | next | head
        ------\
               \
                > ------       ------ 
                 | next | --->| next |--->NULL
                  ------       ------
************************************/

#define _LIST_S
#define _LIST_T

typedef struct list_s {
	struct list_s * next;	
} list_t;

#define init_head_list_t(head) do {            \
		(head)->next = (head);         \
	} while(0)


/**
  @name: list_is_empty
  @function: judge the list is empty or not
  @param: #const list_t * head# list head
  @return: #bool# true is represent for empty list, false is represent for not empty list  
  @algorithm complexity: O(1)
*/
bool list_is_empty(const list_t * head);  

/**
  @name: list_add_head
  @function:Insert a new entry after the specified head.
  @param: #list_t * head# list head to add it after
  @param: #list_t * new# new entry to be added
  @return: #void#
  @algorithm complexity: O(1)
*/
void list_add_head(list_t * head, list_t * new);

/**
  @name: list_add_tail
  @function: Insert a new entry after the specified tail.
  @param: #list_t * head# list head to add it tail 
  @param: #list_t * new# new entry to be added at the tail of list
  @return: #void#
  @algorithm complexity: O(n) 
*/
void list_add_tail(list_t * head, list_t * new);

/**
  @name: list_insert
  @function: insert a new entry after the specified entry
  @param: #list_t * entry# list entry to add it after
  @param: #list_t * new# new entry to be added
  @return #void#
  @algorithm complexity: O(1) 
*/ 
void list_insert(list_t * entry, list_t * new);

/**
  @name: list_del
  @function: delete a entry from the list that entry in it
  @param: #list_t * head# list head that the entry in it
  @param: #list_t * entry# the entry to be deleted
  @return: #void#
  @algorithm complexity: O(n)
*/
void list_del(list_t * head, list_t * entry);

/**
  @name: list_empty
  @function: emtpy the list
  @param: #list_t * head# list head 
  @return: #void#
  @algorithm complexity: O(1)
*/
void list_empty(list_t * head);

/**
  @name: list_is_exist
  @function: judge entry in head or not
  @param: #const list_t * head# list head
  @param: #const list_t * entry# list unit
  @return #bool# true is exist , false is nout exist
  @algorithm complexity: O(n)
*/
bool list_is_exist(const list_t * head, const list_t * entry);

/*********************************
c_list model:
               ------
              | next |  head
               ------  
            /          < 
           /            \
          /              \
         <                \
   ------    ------         ------ 
  | next |->| next |->...->| next |
   ------    ------         ------
*********************************/

#define _C_LIST_S
#define _C_LIST_T

typedef struct c_list_s {
	struct c_list_s * next;
} c_list_t;

#define init_head_c_list_t(head) do {       \
	(head)->next = (head);              \
	} while(0)

/**
  @name: c_list_is_empty
  @function: judge the list is empty or not
  @param: #const c_list_t * head# list head
  @return: #bool# true is represent for empty list, false is represent for not empty list  
  @algorithm complexity: O(1)
*/
bool c_list_is_empty(const c_list_t * head);

/**
  @name: c_list_add_head
  @function: Insert a new entry after the specified head.
  @param: #c_list_t * head# list head to add it after
  @param: #c_list_t *new# new entry to be added
  @return: #void#
  @algorithm complexity: O(1)
*/
void c_list_add_head(c_list_t * head, c_list_t * new);

/**
  @name: c_list_add_tail
  @function: Insert a new entry after the specified tail.
  @param: #c_list_t * head# list head to add it tail
  @param: #c_list_t * new# new entry to be added at the tail of list
  @return: #void#
  @algorithm complexity: O(n)
*/
void c_list_add_tail(c_list_t * head, c_list_t * new);

/**
  @name: c_list_insert
  @function: insert a new entry after the specified entry
  @param: #c_list_t * entry# list entry to add it after
  @param: #c_list_t * new# new entry to be added
  @return: #void#
  @algorithm complexity: O(1)
*/
void c_list_insert(c_list_t * entry, c_list_t * new);

/**
  @name: c_list_del
  @function: delete a entry from the list that entry in it
  @param: #c_list_t * head# list head that the entry in it
  @param: #c_list_t * entry# the entry to be deleted
  @return: #void#
  @algorithm complexity: O(n)
*/
void c_list_del(c_list_t * head, c_list_t * entry);

/**
  @name: c_list_empty
  @function: emtpy the list
  @param: #c_list_t * head# list head 
  @return: #void#
  @algorithm complexity: O(1)
*/
void c_list_empty(c_list_t * head);

/**
  @name:c_list_is_exist
  @function:judge the entry in head or not in 
  @param: #const c_list_t * head# list head
  @param: #const c_list_t * entry# list unit
  @return: #bool# true is exist , false isn't exist
  @algorithm complexity: O(n)
*/
bool c_list_is_exist(const c_list_t * head,const c_list_t * entry);

/*********************************
dlist model:
               ------
head          | prev | <
               ------   \
              | next |   \ 
               ------ \   \
            / >        \   \_______
           / /          \          \ 
          / /            \          \
         < /              >          \
   ------ /                ------    /
  | prev | <--  ...  <--  | prev |  /    
   ------                  ------  /
  | next | -->  ...  -->  | next |/
   ------                  ------
*********************************/

#define _DLIST_S
#define _DLIST_T
typedef struct dlist_s {
	struct dlist_s * prev;
	struct dlist_s * next;
} dlist_t;

#define init_head_dlist_t(head) do {       \
	(head)->prev = (head);               \
	(head)->next = (head);               \
	} while(0)

/**
  @name: dlist_is_empty
  @function: judge the list is empty or not
  @param: #const dlist_t * head# list head
  @return: #bool# true is represent for empty list, false is represent for not empty list  
  @algorithm complexity: O(1)
*/
bool dlist_is_empty(const dlist_t * head);

/**
  @name: dlist_add_head
  @function: Insert a new entry after the specified head.
  @param: #dlist_t * head# list head to add it after
  @param: #dlist_t * new# new entry to be added
  @return: #void#
  @algorithm complexity: O(1)
*/
void dlist_add_head(dlist_t * head, dlist_t * new);

/**
  @name: dlist_add_tail
  @function: Insert a new entry after the specified tail.
  @param: #dlist_t * head# list head to add it tail
  @param: #dlist_t * new# new entry to be added at the tail of list
  @return: #void#
  @algorithm complexity: O(1)
*/
void dlist_add_tail(dlist_t * head, dlist_t * new);

/**
  @name: dlist_insert
  @function: insert a new entry after the specified entry
  @param: #dlist_t * entry# list entry to add it after
  @param: #dlist_t * new# new entry to be added
  @return: #void#
  @algorithm complexity: O(1)
*/
void dlist_insert(dlist_t * entry, dlist_t * new);

/**
  @name: dlist_del
  @function: delete a entry from the list that entry in it
  @param: #dlist_t * head# list head that the entry in it
  @param: #diist_t * entry# the entry to be deleted
  @return: #void#
  @algorithm complexity: O(1)
*/
void dlist_del(dlist_t * head, dlist_t * entry);


/**
  @name: dlist_empty
  @function: emtpy the list
  @param: #dlist_t * head# list head 
  @return: #void#
  @algorithm complexity: O(1)
*/
void dlist_empty(dlist_t * head);

/**
  @name: dlist_is_exist
  @function: judge the entry in head or not in
  @param: #const dlist_t * head# dlist head
  @param: #const dlist_t * entry# dlist unit
  @return: #bool# true is exist and false is not exist
*/
bool dlist_is_exist(const dlist_t * head, const dlist_t * entry); 

#endif /* _LIST_H_ */
